#include<iostream>
#include<vector>
using namespace std;
/*
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
解题思路：
假设dp[i][j]表示从下标i到j的子串中含有最长的回文子序列的长度
假设s=abcdcba,同时i=0，j=6,此时s[i]==s[j]所以有dp[i][j] = dp[i+1][j-1]+2(将s[i],s[j]加入到前一个状态中)
当s[i]!=s[j]时，则要看不考虑s[i]和不考虑s[j]的情况那种情况的回文子序列长度最大
dp[i][j] = max(dp[i+1][j],dp[i][j-1])
但是如何确定初始状态的值呢，首先末尾状态依赖于前面的中间子串，当i==j时中间子串只有一个元素
所以要初始化为dp[i][i] = 1;
如何确定递推方向?
由于dp[i]是由i+1和j-1推导而来,所以采用自左向右自下向上顺序
*/
int dp(string s)
{
    //创建dp数组
    vector<vector<int>> dp(s.size(),vector<int>(s.size()));
    //初始化
    for(int i=0;i<s.size();i++)
        dp[i][i]=1;
    //遍历顺序
    for(int i=s.size()-1;i>=0;i--)
    {
        for(int j=i+1;j<s.size();j++)
        {
            if(s[i]==s[j])
                dp[i][j] = dp[i+1][j-1]+2;
            else
                dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
        }
    }
    return dp[0][s.size()-1];
}
int main()
{  
    cout<<"enter s:"<<endl;
    string s;
    cin>>s;
    cout<<dp(s);
    return 0;
}
